网络数据中的谱聚类算法简述

今天要和大家分享的是网络数据中的谱聚类算法及相关推广，我们将结合Rohe (2011)的Spectral clustering and the high-dimensional stochastic block model进行介绍。此外，针对复杂网络数据，我们将补充几种谱聚类算法的推广方法。

网络数据中的谱聚类算法介绍

谱聚类是一种来源图论的算法，利用网络节点之间的相似性，通过对图的切割来识别节点的社区属性。自Fiedler (1973)以及Donath和Hoffman (2000) 的研究以来，由于谱聚类算法的灵活性以及计算简便的优越性被广泛用于网络社区检测。直观来说，网络社区检测就是将网络节点分为不同社区，使得社区内部节点之间连接稠密，社区之间节点连接稀疏（可参见图1）。下面将具体介绍谱聚类算法是如何实现网络节点社区划分的。

图1: 网络社区检测示意图

在这里我们先引入一些必要的网络数据相关符号。对于给定的带有个节点的网络，记网络节点集合为，用集合表示网络连接集合。通常的，网络节点之间的连接关系可以用网络邻接矩阵表示，即，若节点与节点之间有连接则，否则。特别的，我们约定，也就是说邻接矩阵是一个对角元素为的对称矩阵。另外，谱聚类分析方法重要工具为图拉普拉斯矩阵，这里表示网络度矩阵, 其中节点的度为 。在研究中，为了分析方便，应用更加广泛的是正则化的拉普拉斯。下面我们将介绍基于正则化拉普拉斯矩阵的谱聚类算法。

假设给定的网络 可划分为个社区。谱聚类算法的实现过程主要可分为三步：首先，我们根据获得的邻接矩阵计算图正则化拉普拉斯矩阵。然后，利用谱分析方法将网络节点embedding（嵌入）到维空间。具体地，对正则化拉普拉斯矩阵进行特征分解，获取其最大特征值对应的特征向量，然后按列组成一个特征矩阵，这里我们把特征矩阵的每一行看作是对应节点的embedding 向量，即，其中表示节点的embedding 向量。最后，对特征矩阵的行进行k-均值聚类，则可得到整个网络节点的划分结果。针对用于网络社区检测的谱聚类算法流程可参考图2。关于该算法的详细研究内容可参考Von Luxburg (2007), Newman (2010), Chaudhuri(2012)以及Lei (2015)等。

图2：谱聚类算法流程图

谱聚类分析方法已经广泛应用于诸多领域，例如Bach 和Jordan (2009) 使用谱聚类分析方法来解决语音分离问题，并提出一种盲分离算法; Chasanis等(2008) 通过改进谱聚类算法开发了一种新的视频场景分割方法; Zeng等(2011) 应用频谱聚类分析方法来识别手写数字，另外谱聚类算法在图像分割上也有广泛的应用 (Tung等，2010；Liu等2010；Wang和Dong，2012)。接下来，本文将针对复杂网络数据的社区检测问题，介绍一些关于网络数据中谱聚类算法的推广方法。

网络数据中的谱聚类分析方法推广

在应用谱聚类分析方法实现网络社区检测的过程中，针对不同类型的网络，通常需要对经典谱聚类分析方法进行改进。下面我们将介绍几种常见的网络类型以及对应的谱聚类改进方法。

2.1 针对稀疏网络的谱聚类算法改进

稀疏网络是指网络中的节点与节点之间连接稀疏（见图3），因此邻接矩阵中的非零元素比较少，通常用网络节点的平均度来刻画网络的稀疏程度。记网络节点数为N，若网络节点的平均度小于log⁡(N)，Rohe等(2011)，Joseph等(2016)以及Jing等(2021)指出经典的谱聚类算法不能很好的识别网络节点的社区属性。直观上来说，当网络极度稀疏时会存在较多孤立节点，通常很难根据连接信息估计这些节点的社区标签（如图3所示）。然而，在大数据时代的背景下，大量的实际网络都是稀疏网络，以微博社交平台为例，若两个用户相互关注，则认为两个用户之间存在连接，否则无连接。考虑到大部分用户的粉丝数相比于微博注册用户数量（超5亿）而言是非常少的，这是一个稀疏的社交网络。基于实际应用的驱动，需要将谱聚类算法推广到稀疏网络。

图3: 稀疏网络图，其中E(d)表示网络平均度

目前关于稀疏网络的谱聚类已有很多研究，例如Amini等（2013）提出了带有扰动的谱聚类算法，其主要想法是在所有的节点对之间添加“弱连接“。具体来说，通过在邻接矩阵的每个元素上增加扰动参数，得到正则化邻接矩阵，其中表示所有元素为1的向量。Jing等（2021）年提出SLIM方法解决稀疏网络社区检测问题，该方法利用随机游走理论定义了新的相似矩阵，其中为参数其推荐取值为。该相似矩阵通过刻画各个节点对连接的可能性，充分挖掘节点之间的连接信息，更好的衡量节点之间的相似性，从而能有效估计节点的社区属性。

2.2 针对度异质性网络的谱聚类改进

度异质性网络是指在社区内网络节点的度差异很大，如图4所示的Adamic and Glance (2005) 收集的政治博客网络，蓝色，红色表示用户所属政治社区，网络节点的大小与节点的度成正比。我们可以观察到，同一社区内不同节点度的存在明显差异。此时，根据Qin(2013)以及Joseph(2016)的研究显示，传统的谱聚类算法识别网络节点的社区属性正确率只有51%。Jin (2015) 提出了SCORE方法，该方法利用特征向量比减少网络度异质性的影响。具体的算法流程为：首先，计算特征矩阵，然后，获取个比率特征向量以及比率特征矩阵。最后，对该矩阵的行向量进行k-均值聚类可获得整个网络节点的社区划分结果。

图4: 政治博客网络

2.3 针对混合属性节点网络的谱聚类算法改进

混合属性节点网络是指网络中的节点可具有多个社区属性，这区别于传统的对于数据只具有单一社区属性假设。这种具有混合属性节点的网络实际上是很普遍的，比如科研工作者网络，很多科研工作者兴趣非常广泛在很多研究领域都有建树，那么用传统的聚类方法就无法刻画数据的多面特征。因此，Airoldi (2008)提出如下混合属性模型，

其中，区块矩阵表示社区节点间的连接概率，表示维混合属性向量，为节点的社区属性指示向量，衡量,之间的相似程度。通过参数估计方法，我们可以得到各个节点的混合属性向量的估计，该向量可用来刻画对应节点的多个社区属性特征。

小结

上面我们介绍了谱聚类算法在网络社区检测问题中的应用，也提到针对复杂网络谱聚类算法的相关改进算法。虽然谱聚类算法有成熟的理论保证，并且该算法在应用上也比较简便。但是针对大规模网络数据，目前的谱聚类分析方法依然存在挑战，比如，考虑到谱聚类算法的计算复杂度为，那么针对大规模网络数据，需要进一步降低谱聚类算法的计算成本，有关谱聚类算法的快速计算，一方面可以通过利用快速SVD方法(Halko,2011; Feng, 2018)，另一方面可以利用随机投影(Zhang, 2020)或子抽样方法(Deng, 2021)进行算法改进。另外，由于传统谱聚类算法是同时计算所有网络节点的embedding向量，那么针对动态网络如何实现动态社区识别。这些都是非常有趣的研究方向。

参考文献

[1] Rohe, K., Chatterjee, S., & Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4), 1878-1915.

[2] Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2), 298-305.

[3] Donath, F., Quispe, S., Diefenbach, K., Maurer, A., Fietze, I., & Roots, I. (2000). Critical evaluation of the effect of valerian extract on sleep structure and sleep quality. Pharmacopsychiatry, 33(02), 47-53.

[4] Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and computing, 17(4), 395-416.

[5] Joseph, D. L., & Newman, D. A. (2010). Emotional intelligence: an integrative meta-analysis and cascading model. Journal of applied psychology, 95(1), 54.

[6] Sun, J. Y., Zhao, X., Illeperuma, W. R., Chaudhuri, O., Oh, K. H., Mooney, D. J., ... & Suo, Z. (2012). Highly stretchable and tough hydrogels. Nature, 489(7414), 133-136.

[7] Lei, J., & Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1), 215-237.

[8] Fukumizu, K., Bach, F. R., & Jordan, M. I. (2009). Kernel dimension reduction in regression. The Annals of Statistics, 37(4), 1871-1905.

[9] Chasanis, V., Likas, A., & Galatsanos, N. (2008, October). Video rushes summarization using spectral clustering and sequence alignment. In Proceedings of the 2nd ACM TRECVid Video Summarization Workshop (pp. 75-79).

[10] Zeng, S., Sang, N., & Tong, X. (2011, December). Hand-written numeral recognition based on spectrum clustering. In MIPPR 2011: Pattern Recognition and Computer Vision (Vol. 8004, p. 80040X). International Society for Optics and Photonics.

[11] Liu, H. Q., Jiao, L. C., & Zhao, F. (2010). Non-local spatial spectral clustering for image segmentation. Neurocomputing, 74(1-3), 461-471.

[12] Tung, F., Wong, A., & Clausi, D. A. (2010). Enabling scalable spectral clustering for image segmentation. Pattern Recognition, 43(12), 4069-4076.

[13] Wang, L., & Dong, M. (2012). Multi-level low-rank approximation-based spectral clustering for image segmentation. Pattern Recognition Letters, 33(16), 2206-2215.

[14] Jing, B., Li, T., Ying, N., & Yu, X. (2021). Community detection in sparse networks using the symmetrized laplacian inverse matrix (slim). Statistica Sinica.

[15] Amini, A. A., Chen, A., Bickel, P. J., & Levina, E. (2013). Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, 41(4), 2097-2122.

[16] Adamic, L. A., & Glance, N. (2005, August). The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery (pp. 36-43).

[17] Qin, T., & Rohe, K. (2013). Regularized spectral clustering under the degree-corrected stochastic blockmodel. arXiv preprint arXiv:1309.4111.

[18] Jin, J. (2015). Fast community detection by SCORE. The Annals of Statistics, 43(1), 57-89.

[19] Airoldi, E. M., Blei, D. M., Fienberg, S. E., & Xing, E. P. (2008). Mixed membership stochastic blockmodels. Journal of machine learning research.

[20] Deng, J., Ding, Y., Zhu, Y., Huang, D., Jing, B., & Zhang, B. (2021). Subsampling Spectral Clustering for Large-Scale Social Networks. arXiv preprint arXiv:2110.13613.

[21] Zhang, H., Guo, X., & Chang, X. (2020). Randomized spectral clustering in large-scale stochastic block models. arXiv preprint arXiv:2002.00839.

[22] Halko, N., Martinsson, P. G., & Tropp, J. A. (2011). Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2), 217-288.

[23] Feng, X., Yu, W., & Li, Y. (2018). Faster matrix completion using randomized SVD. In 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 608-615). IEEE.

- END -

点击“查看原文”查看更多精彩